package lanqiao.真题.第13届决赛JavaB组;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 【问题描述】
 * 小蓝面前有N件物品，其中第i件重量是Wi,价值是Vi。她还有一个背
 * 包，最大承重是M。
 * 小蓝想知道在背包称重范围内，她最多能装总价值多少的物品？
 * 特别值得一提的是，小蓝可以使用一个魔法（总共使用一次），将一件物品的重量增加K,同时价值翻倍。（当然小蓝也可以不使用魔法）
 * 【输入格式】
 * 第一行包含3个整数N、M和K。
 * 以下N行，每行两个整数Wi和Vi。
 * 【输出格式】
 * 一个整数代表答案。
 * 【样例输入】
 * 3	10	3
 * 5	10
 * 4	9
 * 3	8
 * 【样例输出】
 * 26
 * 【样例说明】
 * 选择第二件和第三件物品，同时对第二件物品使用魔法。
 * 【评测用例规模与约定】
 * 对于30%的数据，1≤N,M,K≤100.
 * 对于100%的数据，1≤N≤2000,1≤M,K≤10000,0≤Wi,Vi≤10000.
 * @since 2023-06-03 15:17
 */
public class G_背包与魔法 {
}

//部分点超时
class MainG {
    static int N = 2001;
    static int[] weights = new int[N];
    static int[] values = new int[N];
    static int n, m, k;
    static long ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        for (int i = 0; i < n; i++) {
            weights[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }

        int[] dp = new int[m + 1];
        //不使用魔法
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        ans = Math.max(ans, dp[m]);

        //对一件物品使用魔法
        int cur = 0;
        while (cur < n) {
            int weight, value;
            Arrays.fill(dp, 0);
            for (int i = 0; i < n; i++) {
                weight = weights[i];
                value = values[i];
                if (i == cur) {
                    weight += k;
                    value *= 2;
                }
                for (int j = m; j >= weight; j--) {
                    dp[j] = Math.max(dp[j], dp[j - weight] + value);
                }
            }
            ans = Math.max(ans, dp[m]);
            cur++;
        }
        System.out.println(ans);
    }
}
//优化
class MainG1 {
    static int N = 2001;
    static int[] weights = new int[N];
    static int[] values = new int[N];
    static int n, m, k;
    static long ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        for (int i = 0; i < n; i++) {
            weights[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }
        //dp[i] 未使用魔法，i 承重的背包可以取得到最大价值
        int[] dp = new int[m + 1];
        //dp[i] 最多使用一次魔法，i 承重的背包可以取得到最大价值
        int[] dp2 = new int[m + 1];
        //不使用魔法
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
                //当前物品不使用魔法
                dp2[j] = Math.max(dp2[j], dp2[j - weights[i]] + values[i]);
                if (j >= weights[i] + k) {
                    //当前物品使用魔法（前面物品不能使用魔法）
                    dp2[j] = Math.max(dp2[j], dp[j - weights[i] - k] + 2 * values[i]);
                }
            }
        }
        ans = Math.max(dp[m], dp2[m]);
        System.out.println(ans);
    }
}
